package com.sicheng.lc.lc笔试.美团篇;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/13 16:53
 */
public class 生活在树上 {
    //生活在树上
    /**
     * 给一棵有n个节点的二叉树，节点的编号从1到n。
     * 其中，节点k的左儿子为节点2*k（当2*k大于n时，不存在左儿子）
     * 节点k的右儿子为节点2*k+1（当2*k+1大于n时，不存在右儿子）
     * 该二叉树的根节点为节点1。
     * 对于每个节点，节点上有一些金钱。
     *
     * 现在你可以从根节点1开始，每次选择左儿子或者右儿子向下走，直到走到叶子节点停止，并获得你走过的这些节点上的金钱。
     * 你的任务是求出你可以获得的最大的金钱总量。
     * 输入描述
     * 第一行是一个正整数n，表示二叉树上总共有n个节点。
     *
     * 第二行有n个正整数，第i个正整数表示节点i上有多少数量的金钱。
     * 1 <= n <= 100000
     *
     * 对所有数据保证：单个节点上的金钱数量在 [1, 1000] 之间
     *
     * 输出描述
     * 一行一个正整数，表示你所能获得的最大的金钱总量
     * 样例输入
     * 3
     * 5 7 8
     * 样例输出
     * 13
     *
     * 提示
     * 样例解释1
     *
     * 该样例中，二叉树上有三个节点，根节点为1号节点，其左儿子为2号节点，右儿子为3号节点，所能获取的最大金钱为13，为从1号节点走到3号节点，共获得5 + 8 = 13的金钱。
     * 输入样例2
     *
     * 5
     *
     * 863 163 396 428 90
     * 输出样例2
     *
     * 1454
     */
    static int N = 100000;
    static int n;
    static int[] tree = new int[N + 1];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        for (int i = 1; i <= n; i++) {
            tree[i] = in.nextInt();
        }
        long res = dfs(1);
        System.out.println(res);
    }

    static long dfs(int u) {
        if (u > n) {
            return 0;
        }
        long l = dfs(u << 1);
        long r = dfs(u << 1 | 1);
        return Math.max(l, r) + tree[u];
    }
}
